%Preâmbulo
\documentclass[12pt,a4paper]{article}
\usepackage{amssymb,amsmath,amsthm, mathtools}
\usepackage[usenames,dvipsnames]{color}
%\usepackage{ntheorem}
\newtheorem{hyp}{Hip\'{o}tese} 
\newcounter{subhyp} 
\newcommand{\subhyp}{ 
  \setcounter{subhyp}{0} 
  \renewcommand\thehyp{\protect\stepcounter{subhyp}% 
  \arabic{hyp}\alph{subhyp}\protect\addtocounter{hyp}{-1}} 
} 
\newcommand{\normhyp}{ 
  \renewcommand\thehyp{\arabic{hyp}} 
  \stepcounter{hyp} 
} 
\newtheorem{theorem}{Teorema}[section]
\newtheorem*{theoremnon}{Teorema}
\newtheorem{lemma}[theorem]{Lema}
\newtheorem{proposition}[theorem]{Proposi\c{c}\~{a}o}
\newtheorem{corollary}[theorem]{Corol\'{a}rio}

%\newenvironment{proof}[1][Prova]{\begin{trivlist}
%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{definition}[1][Defini\c{c}\~{a}o]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
%\newenvironment{example}[1][Examplo]{\begin{trivlist}
%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
%\newenvironment{remark}[1][Remark]{\begin{trivlist}
%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}

%\newcommand{\qed}{\nobreak \ifvmode \relax \else
%      \ifdim\lastskip<1.5em \hskip-\lastskip
%      \hskip1.5em plus0em minus0.5em \fi \nobreak
%      \vrule height0.75em width0.5em depth0.25em\fi}
\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\usepackage{alltt}
\usepackage{tkz-berge}
\usepackage{wrapfig}
%\usepackage{minted}
\usepackage{listings}
\usepackage{subfloat}
\usepackage{url}
\usepackage{cite}
\usepackage{multirow}
\usepackage{unicamplogo}
\usepackage[portuguese]{babel}
\usepackage[T1]{fontenc}
\usepackage[lofdepth]{subfig}
\usepackage[utf8]{inputenc}
\usepackage{textcomp}
%\usepackage{listingsutf8}%linguagem de programação
\usepackage{xcolor}
\usepackage{color}
\usepackage{graphicx}
\usepackage[export]{adjustbox}
\usepackage{wrapfig}
\graphicspath{ {imagens/} }
\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.95,0.95,0.92} 
\definecolor{mygreen}{rgb}{0,0.6,0}
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
\definecolor{mymauve}{rgb}{0.58,0,0.82}
\definecolor{bg}{rgb}{0.85,0.85,0.85}%cor de background: caixa de fundo do código
%Definições para o pacote listings: linguagem de programação
\lstset{
  backgroundcolor=\color{backcolour},   % choose the background color; you must add\usepackage{color}
  basicstyle=\tiny,        % the size of the fonts that are used for the code
  breakatwhitespace=false,         % sets if automatic breaks should only happen at whitespace
  breaklines=true,                 % sets automatic line breaking
  captionpos=b,                    % sets the caption-position to bottom
  commentstyle=\color{mygreen},    % comment style
  escapeinside={\%*}{*)},          % if you want to add LaTeX within your code
  extendedchars=true,              % lets you use non-ASCII characters;
  frame=single,                    % adds a frame around the code
  keepspaces=true,                 % keeps spaces in text, useful for keeping indentation
  keywordstyle=\color{black},       % keyword style
  language=C,                	  % the language of the code
  numbers=left,                    % where to put the line-numbers; possible values are 
  numbersep=5pt,                   % how far the line-numbers are from the code
  numberstyle=\tiny\color{blue}, % the style that is used for the line-numbers
  rulecolor=\color{black},         % if not set, the frame-color may be changed on line-break
  showspaces=false,                % show spaces everywhere adding particular underscores;
  showstringspaces=false,          % underline spaces within strings only
  showtabs=false,                  % show tabs within strings adding particular underscores
  stepnumber=1,                    % the step between two line-numbers. If it's 1, each line will be numbered
  stringstyle=\color{black},     % string literal style
  tabsize=2,                       % sets default tabsize to 2 spaces
  title=\lstname,                   % show the filename of files included with \lstinputlisting; also try caption instead of title
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    extendedchars=false,
    	inputencoding=utf8,
    	literate=%
        {é}{{\'{e}}}1
        {è}{{\`{e}}}1
        {ê}{{\^{e}}}1
        {ë}{{\¨{e}}}1
        {É}{{\'{E}}}1
        {Ê}{{\^{E}}}1
        {û}{{\^{u}}}1
        {ú}{{\'{u}}}1
        {â}{{\^{a}}}1
        {à}{{\`{a}}}1
        {á}{{\'{a}}}1
        {ã}{{\~{a}}}1
        {Á}{{\'{A}}}1
        {Â}{{\^{A}}}1
        {Ã}{{\~{A}}}1
        {ç}{{\c{c}}}1
        {Ç}{{\c{C}}}1
        {õ}{{\~{o}}}1
        {ó}{{\'{o}}}1
        {ô}{{\^{o}}}1
        {Õ}{{\~{O}}}1
        {Ó}{{\'{O}}}1
        {Ô}{{\^{O}}}1
        {î}{{\^{i}}}1
        {Î}{{\^{I}}}1
        {í}{{\'{i}}}1
        {Í}{{\~{Í}}}1
}
\usepackage[right=2.5cm,left=2.5cm,top=2.5cm,bottom=2.5cm]{geometry}
\usepackage{indentfirst}
\usepackage{float}
%PACOTE DO IC
\usepackage{logo-ic-unicamp}
%PACOTE DO IMECC
\usepackage{logo-unicamp}
%REDEFINE O COMANDO RESUMO
\renewcommand\thesubsubsection{\Roman{subsubsection}} 
\newcommand{\resumo}[2]{\noindent{\textsl{\space#1: }#2}\\}
\usepackage[hidelinks]{hyperref}
\usepackage{enumerate}
\usepackage{marginnote}
%Preparando para o PSEUDOCODIGO
\usepackage{algpseudocode}
\usepackage{algorithm}
\makeatletter
\renewcommand{\ALG@name}{Algoritmo}
\makeatother
\makeatletter
\renewcommand{\listalgorithmname}{Lista de Algoritmos}
\makeatother    
% Declaracoes em Português
\floatname{algorithm}{Algoritmo}
\usepackage{caption}
\DeclareCaptionLabelFormat{something}{#2.#1.}
\renewcommand{\algorithmicrequire}{\textbf{\color{blue}{Entrada: }}}
\renewcommand{\algorithmicensure}{\textbf{\color{violet}{Saída: }}}
\algrenewcommand\algorithmicend{\textbf{fim}}
\algrenewcommand\algorithmicdo{\textbf{faça}}
\algrenewcommand\algorithmicwhile{\textbf{enquanto}}
\algrenewcommand\algorithmicfor{\textbf{para}}
\algrenewcommand\algorithmicif{\textbf{se}}
\algrenewcommand\algorithmicthen{\textbf{então}}
\algrenewcommand\algorithmicelse{\textbf{senão}}
\algrenewcommand\algorithmicreturn{\textbf{devolve}}
\algrenewcommand\algorithmicfunction{\textbf{função}}
\algrenewcommand\algorithmicprocedure{\textbf{procedimento}}
% Rearranja os finais de cada estrutura
\algrenewtext{EndWhile}{\algorithmicend\ \algorithmicwhile}
\algrenewtext{EndFor}{\algorithmicend\ \algorithmicfor}
\algrenewtext{EndIf}{\algorithmicend\ \algorithmicif}
\algrenewtext{EndFunction}{\algorithmicend\ \algorithmicfunction}
% O comando For, a seguir, retorna 'para #1 -- #2 até #3 faça'
\algnewcommand\algorithmicto{\textbf{até}}
\algrenewtext{For}[3]%
{\algorithmicfor\ #1 $\gets$ #2 \algorithmicto\ #3 \algorithmicdo}
%Pacote para colocaração de código no uso do MINTED
\usepackage{footnote}
\usepackage{etoolbox}
\usepackage{tcolorbox}
\tcbuselibrary{minted,skins}
\newtcblisting{myc}{
  listing engine=minted,
  colback=bg,
  colframe=black!70,
  listing only,
  minted style=colorful,
  minted language=c,
  minted options={linenos=true,texcl=true},
  left=1mm,
}
\renewcommand\listingscaption{Implementação}
\renewcommand\listoflistingscaption{Lista de Implementações}
\author{Raphael Marques Franco}
\begin{document}
%capa
\begin{titlepage}
\begin{center}
\hspace{0.1cm}\LogoUnicamp\\\vspace{0.2cm}
\Large{\textbf{\textit{Universidade Estadual de Campinas}}} \\\vspace{0.4cm}

\hspace{0.1cm}\LogoIcUnicamp\\\vspace{0.2cm}
\Large{\textbf{\textit{Instituto de Computação}}} \\\vspace{1cm}
\Large{
\textbf{MC458\\\vspace{0.2cm}
\textit{Projeto e Análise de Algoritmos I}\\\vspace{0.4cm}
Relatório\\ Laboratório 1}}\\\vspace{0.4cm}
\large{\textit{"Implementação e comparação de 3 métodos multiplicação polinomial:\\ Método Direto, método de Karatsuba e método FFT"}}\\\vspace{2cm}
\Large{
\textnormal{Alunos: Lucas Henrique Morais RA136640\\
email: \textit{\color{blue}{lhmaster2@gmail.com }}\\\vspace{0.2cm}
 Raphael Marques Franco RA035501\\\vspace{0.2cm}
email: \textit{\color{blue}{poli.unicamp@gmail.com}}\\\vspace{4cm}
Campinas\\\today{}}}
\end{center}
\end{titlepage}
%fim da capa


%Sumario
%fim do Sumario
\resumo{Resumo}{A eficiência em multiplicar polinômios tem uma enorme importância em inúmeras áreas como teoria de códigos, criptografia e processamento de sinais. Este trabalho apresenta uma breve discussão de 3 algoritmos para multiplicação de polinômios: o método ordinário, por força bruta e denominado método direto, o método de Karatsuba e o método FFT. Para isso, expomos o entendimento do problema, a formulação do problema, o desenvolvimento dos algoritmos com suas respectivas análise assintóticas e provas de corretude, a implementação realizado linguagem C e os testes com dados para análise de desempenho.}%colocar informação dos resultados}
\section{Introdução}
%Uma seção introdutória, descrevendo o problema proposto.
%Cinco passo para um pensamento algoritmico bem sucedido estão em vermelho!
\indent Uma questão de cerne: qual a importância dada a multiplicação polinomial e a preocupação em melhorar seu desempenho? Ao observarmos o importante resultado que a série de Taylor nos traz, onde uma série de Taylor é uma expansão de uma função analítica $f(x)$ na vizinhança de um ponto $x=a$, expresso pela equação \ref{taylor}, onde $f^{(n)}(a)$ é a n-ésima derivada avaliada no ponto $a$:\quad\vspace{-1cm}
\begin{center}
\begin{equation} \label{taylor}
f(x)=\sum_{n=0}^{n \to \infty} {\frac{f^{(n)}(a)}{n!}(x-a)^n}
\end{equation}
\end{center}
\indent\quad\: Na modelagem de fenômenos no domínio do contínuo, expresso por equações diferenciais os quais possuem uma base de funções transcendentais como a função exponencial natural para solução destas, à modelagem de fenômenos no domínio discreto por meio de equações de diferenças finitas ou relações de recorrência, cujas soluções podem ser uma base de funções exponenciais, temos em ambos os domínios a validade da equação \ref{taylor}. Assim torna-se possível uma gama de aplicações em inúmeras áreas devido a aproximação polinomial. Logo conhecer de maneira eficiente operações elementares sobre polinômios permite tornar computável uma infinidade de funções de natureza a primeira vista não polinomial. Apenas como citação a importância da multiplicação de polinômios em teoria de códigos temos o uso em códigos corretores, especificamente os códigos \textbf{BCH}(\textit{cyclic error-correcting}). Em processamento de sinais a convolução de dois sinais discretos no tempo se dá pela multiplicação polinomial realizado pela Transformada de Fourier Discreta tendo aplicações na compressão de dados, análise espectral e filtragem de sinais. Em criptografia temos o algoritmo de encriptação \texttt{NTRU} que é uma alternativa ao \texttt{RSA} e a criptografia por curvas elípticas(\texttt{ECC}).\\
\indent Uma implementação de multiplicação polinomial dentro de uma biblioteca bastante conhecida  e de uso em larga escala em aplicações de criptografia, segurança de aplicações para internet e sistemas de computação algébrica é a \texttt{GNU Multiple-Precision Library}, também conhecida como \texttt{GMP}. Esta biblioteca de código aberto para aritmética de precisão arbitrária, opera sobre inteiros, racionais e números de ponto flutuante permitindo  que variáveis tenham um tamanho de bytes variável, sua implementação é realizada em \texttt{linguagem C}. A estrutura polinomial como será visto esta intimamente ligada a multiplicação de números e para multiplicar dois números de forma eficiente de acordo com a implementação existente na \texttt{GMP} temos ao todo a implementação de 7 algoritmos, para entrada de dois números de mesmo tamanho, temos a tabela \ref{table:algomul}:\\
\begin{table}[H]
\begin{center}
    \begin{tabular}{|c|c|c|}
 	\hline
  	\textbf{Algoritmo} 	& 	\textbf{Ordem Assintótica} 	&		\textbf{Limiar} 			\\ 	\hline
   	Basecase 			& 	$O(N^2)$ 					& 		não apresenta			\\ 	\hline
   	Karatsuba 			& 	$O(N^{1.585})$ 				& 		MUL\_TOOM22\_THRESHOLD 	\\ 	\hline
   	Toom-3 				& 	$O(N^{1.465})$ 				& 		MUL\_TOOM33\_THRESHOLD  	\\ 	\hline
   	Toom-4 				& 	$O(N^{1.404})$ 				& 		MUL\_TOOM44\_THRESHOLD  	\\ 	\hline
   	Toom-6.5 			& 	não informado 				& 		MUL\_TOOM6H\_THRESHOLD  	\\ 	\hline
   	Toom-8.5				& 	não informado 				& 		MUL\_TOOM8H\_THRESHOLD  	\\ 	\hline
   	FFT 					& 	$O(N^{(k/(k-1))})$ 			& 		MUL\_FFT\_THRESHOLD   		\\ 	
   	\hline   
	\end{tabular}
\end{center} 
\captionof{table}{Algoritmos para Multiplicação númerica pela GMP para entrada balanceada\protect\footnotemark}
\label{table:algomul}  
 \end{table}
\footnotetext{\url{https://gmplib.org/manual/Multiplication-Algorithms.html\#Multiplication-Algorithms}}
\indent Tipicamente o \textit{Basecase} mencionado na tabela é o nosso algoritmo ordinário ou multiplicação direta. Os demais são utilizados conforme o critério de limiar, ou seja, não basta apenas a ordem assintótica mas é preciso saber em que momento compensa o uso de um algoritmo em detrimento de outro. Este é um fato muito importante que esperamos observar em nosso trabalho. A \texttt{GMP} trabalha então com uma tomada de decisão sob qual algoritmo utilizar a partir do tamanho da entrada fornecida, lembrando que este caso é para entrada balanceadas, no caso de não ser balanceada ela utiliza o Basecase, abaixo do limiar \texttt{MUL\_TOOM22\_THRESHOLD}, após isso ela utiliza \texttt{FFT}.
\section{Modelagem}
%Uma seção descrevendo a modelagem criada, se houver, e também explicando textualmente ideia usada e o funcionamento dos algoritmos projetados para resolver o problema. Os algoritmos também deverão ser detalhados em pseudo-código. Aqui também deverão ser descritas as entradas válidas e as saídas esperadas para os experimentos.
\subsection{{\color{red}Entendendo o problema}}\vspace{0.5cm}
\noindent Sejam os polinômios com coeficientes reais:\vspace{-1cm}
\begin{center}
\begin{equation}
A(x)= c_{A_0}+c_{A_1}x+\dots+c_{A_{n_A-1}}x^{n_A-1}= \sum_{i=0} ^{i=n_A-1}{c_{A_i}x^i} 
$$e$$ 
B(x)= c_{B_0}+c_{B_1}x+\dots+c_{B_{n_B-1}}x^{n_B-1}= \sum_{j=0} ^{j=n_B-1}{c_{B_j}x^j}
\end{equation}
\end{center}
 
\noindent O polinômio resultante da multiplicação de $A(x)$ e $B(x)$ será:\vspace{-1cm}
\begin{center}
\begin{equation}
C(x)=A(x)B(x)= c_{C_0}+c_{C_1}x+...+c_{C_{n_A+n_B-2}}x^{n_{A}+n_{B}-2}=\sum_{k=0}^{k=n_A+n_B-2}{c_{C_k}x^k}
\end{equation}
\end{center}
O grau dos polinômios $A(x)$, $B(x)$ e $C(x)$ serão denotados, respectivamente, como:\vspace{-1cm}
\begin{center}
\begin{equation}
grau[A(x)]=n_{A}-1 \quad \text{,}\quad grau[B(x)]=n_{B}-1\quad \text{e}\quad grau[C(x)]=n_{A} + n_{B}-2
\end{equation}
\end{center}
O número de coeficientes dos polinômios $A(x)$, $B(x)$ e $C(x)$ serão denotados, respectivamente, como:\vspace{-1cm}
\begin{center}
\begin{equation}\label{eq:num}
\#\text{coeffs}[A(x)]=n_{A} \quad \text{,} \quad \#\text{coeffs}[B(x)]=n_{B} \quad \text{e} \quad \#\text{coeffs}[C(x)]=n_{A} + n_{B} -1
\end{equation}
\end{center}  
\subsection{{\color{red}Formulando o problema}}\label{Formulaop}
Conforme observado na formulação do laboratório, não nos preocupamos com $x$ como valor da entrada. Enquanto a saída, apenas os coeficientes resultantes do polinômio $C(x)$. Mas o que seria então, representativamente o valor de x? Caso seu valor assuma o valor 10 ou 2? Teremos que ele representaria a base de um sistema numérico e neste caso para um computador multiplicar por potência de 2 são simples operações de deslocamento de custo muito menor do que uma instrução de multiplicação. Mas o modelo anterior é válido se utilizamos variáveis inteiras para armazenar nossos números, agora a formulação proposta pela atividade armazena estes mesmos coeficientes em ponto flutuante de precisão dupla padrão \textsf{IEEE 754}, logo não é válido descrever multiplicações por potências binárias apenas como simples deslocamentos de bits. Uma pequena análise sobre o espaço de representação ao observarmos o terceiro arquivo de entrada(\textit{dados10000.txt}) possuir polinômios de tamanho $10^4$, logo um dos coeficientes que mais deve apresentar somas e multiplicações é aquele que esta no meio do polinômio resultante, ou seja, ${c_{C_k}}$ tal que $k=\ceil*{n-1}$. Neste caso devemos ter da ordem de $n$ multiplicações e $n-1$ somas. Logo como cada campo dos coeficientes do arquivo de entrada esta no formato decimal podemos ter no limite caso cada ${c_{A_i}}$ e ${c_{B_i}}$ para todo $i$ variando de $0$ até $n-1$ um coeficiente que tem que comportar:
\begin{equation*}
(9+9x+9x^2+\dots+9x^{4999})\times (9+9x+9x^2+\dots+9x^{4999}) \Rightarrow {c_{C_{4999}}}=9999\times9\times9=809919
\end{equation*}
\indent Assim uma representação com \texttt{UNSIGNED INT} segundo o arquivo \textit{limits.h} tem suporte para de 0 até 4294967295($2^{32}-1$). No nosso caso trabalhamos sempre com número inteiros positivos, portanto, se estamos apenas armazenando os coeficientes e não avaliando o polinômio a representação \texttt{UNSIGNED INT} seria suficiente. Apesar de apresentar um limite para o grau do polinômio igual ao número de somas então:
\begin{equation*}
grau[C(x)]_{MAX}=\floor*{\frac{4294967295}{9\times9}}=53024287
\end{equation*}
\indent Mas na prática teriamos que aumentar o tamanho de página ou melhor o tamanho da \textit{stack} destinada a reservar espaço para os vetores, uma vez que este são sequenciais e alocados estaticamente, conforme o modelo fornecido \texttt{esqueleto-karatsuba.c\footnotemark}\footnotetext{\url{http://www.ic.unicamp.br/~fkm/disciplinas/mc458/2014-2s/labs/lab1/esqueleto-karatsuba.c}}\\
\indent Optamos em utilizar o armazenamento numa estrutura dinâmica armazenado em \texttt{HEAP}, chegando até 139GB na máquina de teste, assim conseguimos realizar testes com polinômios da ordem de $10^5$ coeficientes. Resumidamente, existem duas preocupações que são observar se o valor a ser armazenado no coeficiente neste caso um elemento do vetor é capaz de comportar, assim como observar se a quantidade de elementos, os coeficientes, são devidamente alocados em um espaço de memória capaz de comportar o vetor. O primeiro aspecto, causaria uma falha da interpretação do resultado armazenado estando incorreto o resultado, já o último, conforme o tamanho da ordem do polinômio cresce e a quantidade de estruturas utilizadas vemos que a memória torna-se um fator que pode restringir a análise de desempenho do algoritmo provocado pelo efeito de \textit{Thrashing}. Portanto, nosso modelo pressupõe a não ocorrência de swap, assim nossos sistemas deve ter \texttt{vm.swappiness = 0}.\\
\indent No caso da representação em double seria válido enquanto conseguimos representar um inteiro positivo sem perda, neste caso os 51 bits de precisão dão suporte para um intervalo astronômico da ordem de um polinômio da ordem de $2\times 10^{13}$.\\
\indent Operar na representação de ponto flutuante de precisão dupla, neste caso em 8 bytes, exige algumas considerações às quais não serão alvo deste estudo, a priori vamos simplificar o escopo não importando neste momento o local de armazenamento dos coeficientes e sua representação. Mas sabemos que o aprimoramento do algoritmo pode ganhar um desempenho maior se operarmos nos bits com instruções simplificadas como incrementos, decrementos e deslocamentos de bits. Vamos considerar apenas uma abordagem de um nível mais alto e como já exposto não estaremos preocupados com o formato da representação do número real o qual é a base do modelo dos coeficientes dos polinômios idealmente, mas não para o problema proposto pelo laboratório os quais são inteiros positivos.\\
\indent A necessidade em trabalhar-se com a representação em ponto flutuante quando o problema é característico de multiplicação de números inteiros positivos deve-se ao fato de termos na \texttt{FFT} a passagem para o domínio $\mathbb{C}$. Então seria mais fácil trabalhar no domínio $\mathbb{R}$ e escolher um $\epsilon$ adequado para comparar os resultados obtidos em notação ponto flutuante.\\
\subsection{\textbf{FORMULAÇÃO ORDINÁRIA}}
\indent Vamos rever as definições anteriores e expor a seguir a forma ordinária de multiplicação polinomial:\vspace{-1cm}
\begin{center}
\begin{equation}
C(x)=A(x)B(x)=\sum_{k=0}^{k=n_A+n_B-1}{c_{C_k}x^k}=  \sum_{i=0}^{i=n_A-1}{c_{A_i}x^i}\sum_{j=0}^{j=n_B-1}{c_{B_j}x^j} 
\end{equation}
\end{center}
Considerando $n_A=n_B=n$:\vspace{-1cm}
\begin{center}
\begin{equation}\label{eq:codm}
C(x)=A(x)B(x)= \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}{c_{A_i}c_{B_j}}x^{i+j}=\sum_{k=0}^{2n-2}{c_{C_k}x^k}
\end{equation}
\end{center}
Como estamos interessados apenas nos coeficientes podemos ainda simplificar mais a expressão anterior retirando as potências em $x$:\vspace{-1cm}
\begin{center}
\begin{equation}\label{eq:cod} 
{c_{C_{k}}}=\sum_{\substack{i+j=k \\ 0<i,j<n-1}}c_{A_i}c_{B_j}\Rightarrow{c_{C_{k}}}=\sum_{i=0}^{k}{c_{A_i}c_{B_k-i}}
\end{equation}
\end{center}
De acordo com nossa hipótese anterior $n_A=n_B=n$ e olhando a expressão anterior podemos formular o problema combinatório:  existem $2n-1$ coeficientes do polinômio resultante, entretanto, para obter cada coeficiente, $c_{C_k}$, devemos encontrar a soma das multiplicações dos coeficiente $c_{A_i}$ com $c_{B_j}$ possíveis dentro da regra $i+j=k$. Logo para $i$ e $j$ variando variando de $0$ até $n-1$ quantas construções $i+j=k$ conseguimos realizar com $k$ variando de $0$ até $2n-2$? A estrutura deste mesmo problema é visto em um grafo bipartido completo \textbf{$K_{n,n}$} onde de cada vértice $c_{A_i}$ parte $n$ aresta ligando para todos os outros $n$ vértices distintos $c_{B_i}$($0<i<n-1$). Como temos $n$ vértices $c_{A_i}$ com $n$ arestas partindo deste, teremos no total $n^2$ arestas do grafo bipartido completo \textbf{$K_{n,n}$}.\\
\begin{figure}[!ht]
\begin{center}
\label{k33}
\begin{tikzpicture}
   \begin{scope}[rotate=90]
       \SetVertexMath
       \grEmptyLadder[RA=2,RB=4]{3}   
   \end{scope}
    \Edges(	a0,b0,a1,b0,a2,b0,
    			a0,b1,a1,b1,a2,b1,
    			a0,b2,a1,b2,a2,b2)
\end{tikzpicture}
\end{center} 
\caption{$K_{3,3} \text{ estrutura da multiplicação polinomial de grau 2: }(a_2x^2+a_1x+a_0)(b_2x^2+b_1x+b_0)\text{. Total de produtos igual ao número de arestas, neste caso 9.} $}
\end{figure}
Neste laboratório trabalhamos com o caso particular de ambos os polinômios $A(x)$ e $B(x)$ são de mesma ordem.\\
\indent Visto o problema pela maneira como é exposto as entradas e os formatos apresentados, a melhor maneira de vermos este problema é como sendo um problema clássico de multiplicação de inteiros grandes, ou seja, como na entrada nossos coeficientes para dado um polinômio variam de 0 à 9. Então se assumimos que o valor é $x=10$, logo estamos realizando multiplicações na base decimal. Se somarmos os termos dos coeficientes, ou seja, avaliarmos o polinômio teriamos o resultado da multiplicação de dois números inteiros $A$ e $B$, representados no sistema decimal.\\\\
\subsection{\textbf{FORMULAÇÃO KARATSUBA}}
\indent A ideia básica por trás deste método consiste em observar a possibilidade de economizarmos multiplicações. Mas para entender devemos reescrever o problema da seguinte forma os polinômios $A(x)$, $B(x)$ e $C(x)$:\vspace{-0.5cm}
\begin{center}
\begin{equation}
A(x)=a_A(x)\times x^{m_{A}} +b_A(x),\; \text{onde}\quad m_A=\ceil{n_A/2}
\end{equation}
\end{center}
\begin{center}
\begin{equation}\vspace{1cm}
B(x)=c_B(x)\times x^{m_{B}} +d_B(x),\; \text{onde}\quad m_B=\ceil{n_B/2}
\end{equation}
\end{center}
\vspace{-0.5cm}Por simplicidade considere $n_A=n_B=n$ e $m=\ceil{n/2}$, logo $C(x)$ será\footnotemark:\vspace{-0.5cm}
\footnotetext{A escolha $m=\ceil{n/2}$, trata o caso ímpar e par.}
\begin{center}
\begin{eqnarray}
C(x)&=&A(x)\times B(x)=[a_A(x)\times x^{m} +b_A(x)][c_B(x)\times x^m +d_B(x)]\nonumber\\
&=&\color{red}\overbrace{c_A(x)\times c_B(x)}^{1\times}\color{black}\times x^{2m} +(\color{blue}\overbrace{a_A(x)\times d_B(x)}^{2\times}+\overbrace{b_A(x)\times c_B(x)}^{3\times}\color{black})\times x^m+\nonumber\\
&+&\color{red}\overbrace{b_A(x)\times d_B(x)}^{4\times}\label{eq:fkara1}
\end{eqnarray}
\end{center}
\newpage
\vspace{-0.5cm}Considere a definição de $\color{OliveGreen}y(x)$:\vspace{-1cm}
\begin{center}
\begin{eqnarray}
\color{OliveGreen}y(x)\color{black}&=&\color{OliveGreen}\overbrace{(a_A(x)+ b_A(x))\times(c_B(x) + d_B(x))}^{1\times}\color{black} \label{eq:kara1}\\
\color{OliveGreen}y(x)\color{black}&=&\color{red}a_A(x)\times c_B(x)\color{black}+\color{red}b_A(x) \times d_B(x)\color{black}+\color{blue}b_A(x)\times d_B(x)+a_A(x) \times d_B(x)\label{eq:kara2}\\
\color{OliveGreen}y(x)\color{black}&-&\color{red}a_A(x)\times c_B(x)\color{black}-\color{red}b_A(x) \times d_B(x)\color{black}=\color{blue}b_A(x)\times d_B(x)+a_A(x) \times d_B(x) \color{black}\label{eq:kara3}
\end{eqnarray}
\end{center}
\hspace{0.6cm} Então podemos economizar uma multiplicação polinomial da equação \ref{eq:fkara1} visto pela equação \ref{eq:karatsubafinal}, ao calcular apenas as multiplicações polinomiais em verde da equação \ref{eq:kara1} e vermelho da equação \ref{eq:fkara1}. Devido a uma manipulação algébrica na equação \ref{eq:kara2} temos a equação \ref{eq:kara3} que seria equivalente a duas multiplicações polinomiais em azul na equação \ref{eq:fkara1}.\\
\hspace{0.6cm}\indent Assim temos 3 multiplicações polinomiais de polinômios que são metade do tamanho dos polinômios originais:\vspace{-.5cm}
\begin{center}
\begin{eqnarray}\label{eq:karatsubafinal}
C(x)&=&\color{red}\overbrace{(a_A(x)\times c_B(x))}^{1\times}\color{black}\times x^{2m} +(\color{OliveGreen}\overbrace{(a_A(x)+ b_A(x))\times(c_B(x) + d_B(x))}^{2\times}\color{black} \nonumber\\
&-&\color{red}\overbrace{a_A(x)\times c_B(x)}^{\text{repetido}}\color{black}-\color{red}\overbrace{b_A(x) \times d_B(x)}^{\text{repetido}}\color{black})\times x^m+\color{red}\overbrace{b_A(x)\times d_B(x)}^{3\times}\color{black} \nonumber\\
&=& \color{red}a_A(x)\times c_B(x)\color{black}\times x^{2m} +(\color{OliveGreen}y(x)\color{black} -\color{red}a_A(x)\times c_B(x)\color{black}-\color{red}b_A(x) \times d_B(x))\color{black})\times x^m\nonumber\\
&+&\color{red}b_A(x)\times d_B(x)\color{black}
\end{eqnarray}
\end{center}
\vspace{-0.5cm}\subsection{\textbf{FORMULAÇÃO FFT }}
\color{black}
\indent O método FFT advém do fato de novamente reescrevermos o polinômio de uma outra maneira e buscarmos trabalhando dentro de mudanças do espaço dos $\mathbb{R}$ transformado para $\mathbb{C}$ levando às operações as quais sejam menos custosas do que operar com o polinômio original no domínio $\mathbb{R}$(\textit{\underline{Ordinary multiplication}}: de ordem assintótica $\Theta(n^2)$). A figura \ref{fig:awesome_image} ilustra esquematicamente  o algoritmo FFT, em 3 etapas: avaliar o polinômio na representação no espaço complexo através da transformada discreta de Fourier(\textbf{DFT})(\textit{\underline{Evaluation}}: de ordem assintótica $\Theta(n \lg n)$), realizar a multiplicação ponto a ponto(\textit{\underline{Pointwise multiplication}:} de ordem assintótica $\Theta(n)$) e obtido o conjunto resultante representando pontos avaliados nos coeficientes de $C(x)$(\textit{\underline{Point-value representation}}) no domínio $\mathbb{C}$ é realizado a interpolação destes pontos via transformada inversa discreta de Fourier(\textbf{IDFT})(\textit{\underline{Interpolation}}: de ordem assintótica $\Theta(n \lg n)$).
\begin{figure}[H]
\centering
\includegraphics[scale=0.3]{fftdiagram.png}
\caption{Ilustração das transformações e ordens assintóticas envolvidas via método ordinário e FFT para  a multiplicação polinomial, obtida de \cite{cormen2011introduction} página 904.}
\label{fig:awesome_image}
\end{figure}
\indent Revendo a equação \ref{eq:codm}, caso considere que o polinômio $A(x)$ e $B(x)$ estão com seus coeficientes devidamente ajustado em suas respectivas posições, entretanto, queremos ajustar para que ambos possuam coeficientes até o tamanho dos coeficientes do polinômio $C(x)$, ou seja, estamos colocando valor nulo nos coeficientes de grau $n$ até $n-2$ destes novos polinômios $A(x)$ e $B(x)$. Assim a operação vista na equação \ref{eq:cod}, pode ser revista como sendo uma convolução:
\begin{hyp}
\label{eq:considere}
$\text{Para }\forall i\text{ fora do intervalo } 0 \leq i \leq n-1  \text{ tem-se } c_{A_i} = 0 \text{ e } c_{B_i} = 0\text{.}$
\end{hyp}

\begin{definition}
\begin{equation}
{c_{C}}=c_{A} \ast c_{B} \Leftrightarrow {c_{C_{k}}} =  \sum_{i=- \infty}^{\infty}{c_{A_i}c_{B_{k-i}}} \label{eq:exemplo}\\
\end{equation}
\end{definition}
\indent A equação \ref{eq:exemplo2} fica exatamente a equação \ref{eq:cod} aplicando a hipótese \ref{eq:considere}:
\begin{equation}
\xRightarrow{\text{Hip\'{o}tese \ref{eq:considere}}} \; {c_{C_k}} =\sum_{i=0}^{k}{c_{A_i}c_{B_{k-i}}}\:\text{, para }\forall k\text{: } 0 \leq k \leq 2n-1  \label{eq:exemplo2}
\end{equation}
\begin{theoremnon}[\emph{{Grupo Cíclico Finito (números de Moivre, $\times$) isomorfo $(\mathbb{Z}_N,+_{N})$}}]\label{teo:interpola}
O \textbf{Teorema Fundamental da Álgebra} garante  que existem exatamente N raízes complexas da equação $\omega^N=1$, sendo conhecidas as raízes advindas da \textbf{raíz fundamental da unidade} ou primitiva $\omega_{N}=e^{2{\pi}i/N}$, seus múltiplos $\omega_{N}^{k}=e^{2{\pi}ik/N}$ para todo $k=0, 1, \dots, n-1$ são as soluções.  Definindo o conjunto solução $S:=\{\omega_{N}^{0}, \omega_{N}^{1}, \dots, \omega_{N}^{N-1}\}$, conhecidos como \textbf{números de Moivre}. O conjunto $S$ sobre a operação de multiplicação forma um \textbf{grupo cíclico finito}, dizemos que o grupo formado pelo par ordenado $(S, \times)$ é isomorfo ao grupo $(\mathbb{Z}_N,+_{N})$. Um grupo cíclico finito é um grupo gerado por um único elemento, este grupo respeita as propriedades de grupo: associatividade, existência de elemento neutro e existência de elemento simétrico. Por fim, qualquer operação entre quaisquer elementos de $S$ recai em $S$ que é finito sendo totalmente gerado pelo elemento conhecido como raíz fundamental da unidade operando sob este único elemento.\\
\end{theoremnon}
\begin{definition}
Uma sequência de $N$ números complexos $x_{0},x_{1}, /dots, x_{N-1}$ apresenta a transformada discreta de Fourier(DFT)
\begin{equation}\label{eq:dtft}
\mathcal{F}\{X_k\} = \sum_{i=0}^{N-1}x_{X_k}[i]e^{i2\pi\frac{ki}{N}}
\end{equation}
\end{definition}
\indent Definido a transformada Discreta de Fourier($\mathrm{DFT}$), temos uma propriedade importante conhecido como:
\begin{theoremnon}[\emph{Teorema da Convolução}]
\begin{equation}
\mathcal{F}^{-1}\{\mathcal{F}\{X_k\}\mathcal{F}\{Y_k\}\}=x_{X_k}\ast y_{Y_k}
\end{equation}
\end{theoremnon}
\begin{theoremnon}[\emph{\textbf{Unicidade da Interpolação Polinomial}}]\label{teo:interpola}
Um polin\^{o}mio qualquer $P(x)$ de grau $n-1$ é representado pelos seus $n$ coeficientes. Estes podem ser obtidos univocamente obtidos de $n$ pontos: $(x_0,P_0(x_0))$, $(x_1,P_1(x_1))$, $\dots$, $(x_{n-1},P_{n-1}(x_{n-1}))$. Onde $P(x_i)$ consiste avaliar o polinômio $P(x)$ no ponto $x_i$, sendo que para todo $i\neq j$ temos $x_i \neq x_j$.  
\end{theoremnon}
\indent Para avaliar um polinômio qualquer $P(x)$ utilizamos a \textit{regra de Horner}:\vspace{-1cm}
\begin{center}
\begin{equation*}
P(x)= \sum_{i=0}^{n-1}a_{i}x^{i}=a_{0}+x(a_{1}+x(a_2+\dots+x(a_{n-2}x^{n-2}+a_{n-1}x)\dots))
\end{equation*}
\end{center}
\indent Assim como temos $A(x)$ e $B(x)$, avaliamos em $n$ pontos para cada polinômio
\newpage
\subsection{{\color{red}Desenvolvendo o Algoritmo}}
\subsubsection{Método Ordinário}
\begin{algorithm}[!ht]
\algorithmicrequire{\\
\Comment{\color{blue}{$A[0..n-1]$}\, Vetor A contendo os coeficientes do polinômio $A(x)$}\\
\Comment{\color{blue}{$B[0..n-1]$}\, Vetor B contendo os coeficientes do polinômio $B(x)$}\\ 
\Comment \color{blue}{$n$}\, Número de coeficientes do polinômio A ou B}\\
\algorithmicensure{\\
\Comment{\color{violet}{$C[0..2n-2]$} Vetor C de coeficientes do polinômio $C(x)=A(x)B(x)$}\\}
\caption{\textbf{Método Direto}}\label{alg:quadpseudo}
\begin{algorithmic}[1]
\Function{$multpoli\_quad$}{$n$, $\mathbf{A}$, $\mathbf{B}$, $\mathbf{C}$}
\For{i}{0}{2n-2} \Comment{polinômio $C(x)$ tem $2n-1$ coeficientes, equação \eqref{eq:num}}
	 \State $C[i] \gets 0$\Comment{Inicializa o vetor \textbf{C}}
\EndFor
\For{i}{0}{n-1}
	\For{j}{0}{n-1}
		\State $C[i+j]\gets C[i+j]+A[i]B[j]$ \Comment{equação \eqref{eq:cod}}
	\EndFor
\EndFor
\EndFunction
\end{algorithmic}
\end{algorithm}
\hspace{-.6cm}\textbf{Prova de Corretude:}\\\\
\indent Como visto anteriormente na seção \ref{Formulaop}, obtemos a equação \eqref{eq:cod} a qual esta implementada na linha 7  e o conjunto das linhas 5, 6 e 7 equivalem a equação \eqref{eq:codm}, estas referentes ao algoritmo \ref{alg:quadpseudo}. Logo devemos mostrar o problema da parada, além disso algoritmo resolve a menor instância possível e qualquer outra instância. \\\\
\color{black}
\textbf{Análise Assintótica}:\\\\
\indent Das linhas finais do tópico \textit{Formulando o problema}(\ref{Formulaop}) no método ordinário devemos ter:\vspace{-1.0cm}
\begin{center}
\begin{equation*}
T(n)= n^2(\text{produtos})+ \sum_{i=0}^{i=n-1}i(\text{somas})
\end{equation*}
\end{center}
\hspace{.1cm}\indent Mas estamos interessados apenas nas operações mais custosas, as multiplicações. Logo, assintoticamente: \vspace{-1cm}
\begin{center}
\begin{equation*}
T(n)=O(n^2)
\end{equation*}
\end{center}
\hspace{.1cm}\indent Podemos aferir diretamente no algoritmo através da contagem do pseudo-código do número de multiplicações que ocorre na linha 7, visto pela repetição dos laços da linha 5 e 6, cada um contribuindo com n repetições. Assim $n^2$ multiplicações ou ocorrências da linha 7.\\\\
\newpage
\subsubsection{Karatsuba}
\begin{algorithm}[H]
\algorithmicrequire{\\
\Comment{\color{blue}{$A[0..n-1]$}\, Vetor A contendo os coeficientes do polinômio $A(x)$}\\
\Comment{\color{blue}{$B[0..n-1]$}\, Vetor B contendo os coeficientes do polinômio $B(x)$}\\ 
\Comment \color{blue}{$n$}\, Número de coeficientes do polinômio A ou B}\\
\algorithmicensure{\\
\Comment{\color{violet}{$C[0..2n-2]$} Vetor C de coeficientes do polinômio $C(x)=A(x)B(x)$}\\}
\caption{\textbf{Karatsuba}}
\label{alg:karatsubapseudo}
\begin{algorithmic}[1]
\Function{$multpoli\_kara$}{$n$, $\mathbf{A}$, $\mathbf{B}$, $\mathbf{C}$}
\For{i}{0}{2n-2} \Comment{polinômio $C(x)$ tem $2n-1$ coeficientes, equação \eqref{eq:num}}
	 \State{$C[i] \gets 0$}\Comment{Inicializa o vetor \textbf{C}}
\EndFor
\If {$n \leq \Omega \footnotemark$}
	\State {$multpoli\_quad$($n$, $\mathbf{A}$, $\mathbf{B}$, $\mathbf{C}$)}
\Else
	\State {$m \gets \ceil*{n/2}$}\Comment{a entrada n pode ser qualquer: par ou ímpar}
	\State {$\mathbf{a_A}[0\:..\:n-m-1] \gets \mathbf{A}[m\;..\:n-1]$}\Comment{divide o vetor A em parte alta}
	\State {$\mathbf{b_A}[0\:..\:m-1] \gets \mathbf{A}[0\:..\:m-1]$}\Comment{divide o vetor A em parte baixa}
	\State {$\mathbf{c_B}[0\:..\:n-m-1] \gets \mathbf{B}[m\:..\:n-1]$}\Comment{divide o vetor B em parte alta}
	\State {$\mathbf{d_B}[0\:..\:m-1] \gets \mathbf{B}[0\:..\:m-1]$}\Comment{divide o vetor B em parte baixa}
	\If{	$n$ é ímpar}\Comment{parte baixa e alta tem sempre m elementos}
		\State{$a_A[m-1] \gets 0$}
		\State{$c_B[m-1] \gets 0$}	
	\EndIf
	\State{$multpoli\_kara(m,\: \mathbf{a_A},\: \mathbf{c_B},\: \mathbf{V_{ac}})$} \Comment{\color{red}{$V_{ac} \gets a_A \times c_B$}}
	\color{black}\State{{$multpoli\_kara(m,\: \mathbf{b_A},\: \mathbf{d_B},\: \mathbf{V_{bd}})$}} \Comment{\color{red}{ $V_{bd}\gets b_A \times d_B$}}
	\color{black}\State{$\mathbf{V_{a+b}} \gets Sum(\mathbf{a_A},\mathbf{b_A})$} \Comment{Para $i$ de $0$ até $m-1$, $V_{a+b}[i]=a_A[i] + b_A[i]$}
	\State{$\mathbf{V_{c+d}} \gets Sum(\mathbf{a_A},\mathbf{b_A)}$} \Comment{Para $i$ de $0$ até $m-1$, $V_{c+d}[i]=c_B[i] + d_B[i]$}
	\color{black}\State{$multpoli\_kara(m, \mathbf{V_{a+b}}, \mathbf{V_{c+d}}, \mathbf{y})$} \Comment{\color{red}$y \gets (a_A+b_A)\times(c_B+d_B)$}
	\color{black}\State{$\mathbf{V_{ac+bd}}=Sum(\mathbf{V_{ac}}, \mathbf{V_{bd}})$}\Comment{$i$ de $0$ até $m-1$, $V_{ac+bd}[i]=V_{ac}[i] + V_{bd}[i]$}
	\State{$\mathbf{V_{y-ac+bd}}=Sub(\mathbf{y}, \mathbf{V_{ac+bd}})$} \Comment{$i$ de $0$ até $m-1$, $V_{y-ac+bd}[i]=y[i] - V_{ac+bd}[i]$}	
	\State{$\mathbf{C}[0\:..\:2m-2] \gets deslocado(\mathbf{V_{ac}},\: 2m) + deslocado(\mathbf{V_{y-ac+bd}},\: m)$}
\EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}
\footnotetext{$\Omega$ é determinado experimentalmente. São realizados execuções com alguns valores que melhorem o tempo de execução do método de Karatsuba ou fator de speedup em relação aos outros métodos para um certo intervalo onde o Karatsuba ganha dos demais. Valor encontrado $\Omega=70$, intervalo considerado de $1000 \leq n \leq  3000$}
\indent Na linha 9 e 11 do algoritmo \ref{alg:karatsubapseudo}, se n é ímpar na divisão do vetor $A$ e $B$, a parte alta tem o mesmo número de elementos da parte baixa, ou seja, m elementos sendo $a_A[m-1] \gets 0$ e $c_B[m-1] \gets 0$, isto é garantido pelo condicional da linha 13 e as ações das linhas 14 e 15.
\begin{algorithm}[H]
\algorithmicrequire{\\
\Comment{\color{blue}{$K[0..l-1]$}\, Vetor K contendo os coeficientes do polinômio $K(x)$}\\ 
\Comment \color{blue}{$m$}\, deslocamento}\\
\algorithmicensure{\\
\Comment{\color{violet}{$W[0..2n-2]$} Vetor W de coeficientes do polinômio $W[m..l+m-1] \gets K[0..l-1]$}\\}
\caption{\textbf{Deslocado}}\label{alg:desloca}
\begin{algorithmic}[1]
\Function{deslocado}{\textbf{W}, m}
\For{i}{0}{m} \Comment{polinômio $C(x)$ tem $2n-1$ coeficientes, equação \eqref{eq:num}}
	 \State{$W[l-1+i] \gets k[i]$}\Comment{copia o valor na posição do deslocamento}
\EndFor
\EndFunction
\end{algorithmic}
\end{algorithm}
\hspace{-.6cm}\textbf{Prova de Corretude:}\\
\indent
\color{red}{\textbf{!FALTANDO!}}\\
\color{black}
\textbf{Análise Assintótica:}\\
\indent Para a resolução do problema de tamanho de entrada $n$ são gastos $T(n)$ operações. Observando o pseudo-código do algoritmo \ref{alg:karatsubapseudo} nas linhas 13, 14 e 17 temos das chamadas recursivas, respectivamente, as parcelas $T(\floor*{n/2})$, $T(\ceil*{n/2})$ e $T(\ceil*{n/2})$. A justificativa das escolhas anteriores deve-se ao tamanho do vetores \textbf{$a_A$} e \textbf{$c_B$} são de tamanho $\floor*{n/2}$, enquanto que \textbf{$c_A$} e \textbf{$d_B$}  ou $V_{a+b}$ e $V_{c+d}$ são de tamanho $\ceil*{n/2}$. Sabendo que linhas 9 à 12, 15, 16 e 18 do algoritmo \ref{alg:karatsubapseudo}, tem custo linear e outras operações menores são comparações e atribuições de tempo constante percorrendo um vetor de tamanho linear, visto o algoritmo \ref{alg:desloca}. Portanto, formulamos a expressão:\vspace{-1cm}
\begin{center}
\begin{equation}\label{eq:recp}
T(n) = 2T(\ceil*{n/2})+T(\floor*{n/2})+c_{2}n+c_1
\end{equation}
\end{center}
É valido o Teorema Master(CLRS)\cite{cormen2011introduction}: \vspace{-1cm}
\begin{center}
\begin{equation}
\label{eq:solverecurrencepar}
T(n) = 3T(n/2)+c_{2}n+c_1 
\end{equation}
\end{center}
 O Teorema Master(CLRS) enunciado, no formato:\vspace{-1cm}
\begin{center}
\begin{equation}
\label{eq:teomaster}
T(n) = k_1T(n/k_2)+f(n) 
\end{equation}
\end{center}
Portanto, $k_1=3$, $k_2=2$ e $f(n)=c_{2}n+c_1$, comparando as equações \ref{eq:solverecurrencepar} e \ref{eq:teomaster}. Recaimos no caso 1 do Teorema Master(CLRS):\vspace{-1cm}
\begin{center}
\begin{equation}
\label{eq:solvemastercase1}
f(n)=O(n^{\log_b {a-\epsilon}})\Rightarrow n=O(n^{\log_2 {3-\epsilon}})\quad \exists\epsilon>0,\:\epsilon=0,58 \quad \therefore T(n)=\Theta(n^{\log_2 {3}})
\end{equation}
\end{center}
\newpage
\subsubsection{Método de Schönhage-Strassen}
\begin{algorithm}[!h]
\caption{\textbf{FFT}}
\algorithmicrequire{\\
\Comment{\color{blue}{$A[0\:..\:n-1]$}\, Vetor A contendo os coeficientes do polinômio $A(x)$}\\
\Comment{\color{blue}{$B[0\:..\:n-1]$}\, Vetor B contendo os coeficientes do polinômio $B(x)$}\\ 
\Comment \color{blue}{$n$}\, Número de coeficientes do polinômio A ou B}\\
\algorithmicensure{\\
\Comment{\color{violet}{$C[0\:..\:2n-2]$} Vetor C de coeficientes do polinômio $C(x)=A(x)B(x)$}\\}
\begin{algorithmic}[1]
\Function{multpoli\_fft}{tam, \textbf{A}, \textbf{B}, \textbf{C}}
\For{i}{0}{2n-2} \Comment{polinômio $C(x)$ tem $2n-1$ coeficientes, equação \eqref{eq:num}}
	 \State{$C[i] \gets 0$}\Comment{Inicializa o vetor \textbf{C}}
\EndFor

\EndFunction
\end{algorithmic}
\end{algorithm}

\hspace{-.6cm}\textbf{Prova de Corretude:}\\
\indent
\color{red}{\textbf{!FALTANDO!}}\\\\
\hspace{-.6cm}\textbf{Análise Assintótica:}\\
\indent
\color{red}{\textbf{!FALTANDO!}}\\
\newpage
\color{black}
\section{Estrutura do programa}
%Uma seção descrevendo a estrutura do programa fonte projetado pelo grupo. Dê detalhes suficientes para que a estrutura do fluxo de controle e execução do programa fique clara.
\subsection{{\color{red}Implementando o Algoritmo}}

\begin{minted}
[
frame=single,
framesep=2mm,
baselinestretch=1.2,
bgcolor=bg,
fontsize=\footnotesize,
linenos
]
{c}
#define M_PI	3.14159265358979323846 	//define PI
#define EPS		1e-5		    //diferenca permitida entre
// coeficientes comparado por 2 metodos distintos	
#define MAX 	65536 			//maximo suportado para os
// vetor resultante, logo A e B possuem se iguais metade
// deste valor
typedef unsigned int uint;

struct Polynomial
{
	double *p;
	double size;
};

// Estrutura axiliar para dividir vetores na etapa da Divisao
struct SplitPolynomial
{
	struct Polynomial high;
	struct Polynomial low;
	int split;
};
// Estrutura de representacao na forma apropriada 
// dentro do algoritmo de Karatsuba
struct Z
{
	struct Polynomial z2;
	struct Polynomial z1;
	struct Polynomial z0;
	int split;
};
\end{minted}

\indent Acima estão algumas definições de  estruturas de dados que tem por objetivo tornar mais claro nossa representação, assim como encapsular e auxiliar na modularização do código, visto nas implementações a seguir.

\begin{listing}[H]
/* 
A função recebe um inteiro sendo tamanho do maior número de coeficientes entre dois polinômios, um vetor A contendo os coeficientes reais do polinômio A(x), um vetor B contendo os coeficientes reais do polinômio B(x) e um vetor C que será utilizado para armazenar o resultado, C(x), da multiplicação polinomial realizado por passagem por referência. O código foi modularizado para respeitar a assinatura da função pedida
*/
\caption{Método Direto: $O(n^2)$} 
\begin{minted}
[
frame=single,
framesep=2mm,
baselinestretch=1.2,
bgcolor=bg,
fontsize=\footnotesize,
linenos
]
{c}
/** 
  * Assinatura da especificacao do laboratorio
  */
void multpoli_quad(int n, double A[], double B[], double C[]){
	C = quad_algo(n, A, B);
}
/**
 * Funcao de multplicacao de polinomios segundo algoritmo classico.
 * Dadas duas representacoes polinomiais p1 e p2 de n termos cada,
 * retorna o produto de tais polinomios.
 */
double * quad_algo (int n, double * p1, double * p2){
	double * p = challoc(2 * n - 1, sizeof(double));
	int i, j;
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++){
			p[i + j] += p1[i] * p2[j];
			sum_quad++;
			mult_quad++;
		}
	return p;
}
/**
 * Dados duas representacoes polinomiais p1 e p2, calcula o coeficiente
 * a multiplicar o (exp+1)-esimo termo do produto p1 * p2.
 */
double productCoef (double * p1, double * p2, int exp){
	int i, j;
	double pcoef;
	for (i = 0, j = exp, pcoef = 0; i <= exp; i++, j--){
		pcoef += p1[i] * p2[j];
	}
	return pcoef;
}
\end{minted}
\label{Direto}
\end{listing}\vspace{2cm}
\newpage
\begin{listing}[H]
/* 
Considerações análogas à implementação do método Direto.
*/
\caption{Método Karatsuba: $O(n^\epsilon)$ \protect\footnotemark}
\label{Karatsubaa}
\begin{minted}
[
frame=single,
framesep=2mm,
baselinestretch=1.2,
bgcolor=bg,
fontsize=\footnotesize,
linenos
]
{c}
/** 
  * Assinatura da especificacao do laboratorio
  */
void multpoli_kara(int n, double A[], double B[], double C[]){
	struct Polynomial sA, sB, sC;
	sA.p=A, sB.p=B, sC.p=C,sA.size=n, sB.size=n, sC.size=2*n;
	sC = karat_core(n, sA, sB);
	C=sC.p;
}
struct Polynomial karat_core (int n, struct Polynomial x, struct Polynomial y){
	int split_point;
	struct SplitPolynomial X, Y;
	struct Polynomial resp;
	struct Z zees;
	if (n < 10){
		resp.p = quad_algo(n, x.p, y.p);
		return resp;
	}
	split_point = split_size(n);
	X = split(n, split_point, x);
	Y = split(n, split_point, y);
	zees = computeZ(X, Y);
	resp = compose_poly(zees);
	return resp;
}
struct Z computeZ (struct SplitPolynomial X, struct SplitPolynomial Y){
	struct Z resp;
	resp.z0 = karat_core(X.split*2, X.low, Y.low);
	resp.z2 = karat_core(X.split*2, X.high, Y.high);
	resp.z1 = karat_core(X.split*2, add_coeff(X.high, X.low), add_coeff(Y.high, Y.low));
	resp.z1 = sub_coeff(resp.z1, add_coeff(resp.z2, resp.z0));
	resp.split = X.split;
	return resp;
}
struct SplitPolynomial split (int N, int split_point, struct Polynomial p){
	struct SplitPolynomial sp;
	int i;
	sp.high.p = calloc(N - split_point, sizeof(double));
	sp.high.size = N - split_point;
	sp.low.p  = calloc(split_point, sizeof(double));
	sp.low.size  = split_point;
	for (i = 0; i < split_point; i++){
		sp.low.p[i] = p.p[i];
	}
\end{minted}
\end{listing}\vspace{-3cm}

\footnotetext{\textbf{$\epsilon$} equivale à $\lg 3$ da solução \eqref{eq:solvemastercase1} e concorda com \cite{knuth1997art} seção \textbf{4.3.3} página 295}
\newpage
\begin{listing}[H]
\ContinuedFloat
\setcounter{listing}{2}
\caption{Método Karatsuba: $O(n^\epsilon)$}
\label{Karatsuba}
\begin{minted}
[
frame=single,
framesep=2mm,
baselinestretch=1.2,
bgcolor=bg,
fontsize=\footnotesize,
linenos,
firstnumber=45
]
{c}
	for (i = split_point; i < N; i++){
		sp.high.p[i - split_point] = p.p[i];
	}
	return sp;
}
struct Polynomial compose_poly (struct Z zees)
{
	struct Polynomial resp;
	int i;
	resp.size = zees.z2.size + zees.split;
	resp.p = calloc(resp.size, sizeof(double));
	for (i = 0; i < zees.split; i++){
		resp.p[i] = zees.z0.p[i];
	}
	for (i = zees.split; i < 2 * zees.split; i++){
		resp.p[i] = zees.z1.p[i - zees.split];
	}
	for (i = 2 * zees.split; i < 4 * zees.split; i++){
		resp.p[i] = zees.z2.p[i - 2 * zees.split];
	}
	return resp;
}
\end{minted}
\end{listing}

\begin{listing}[H]
/* 
Considerações análogas à implementação do método Direto.
*/
\setcounter{listing}{2}
\caption{Método FFT: $O(n \lg n \lg \lg n)$}
\label{FFT}
\begin{minted}
[
frame=single,
framesep=2mm,
baselinestretch=1.2,
bgcolor=bg,
fontsize=\footnotesize,
linenos
]
{c}
/** 
  * Assinatura da especificacao do laboratorio
  */
void multpoli_fft (int n, double A[], double B[], double C[]){
	C=fft_algo(n, A, B);
}
double * fft_algo (int n, double * p1, double * p2){
	double *d1, *d2, *d, *p;
	d1 = evaluateDFT(p1, n);
	d2 = evaluateDFT(p2, n);
	d = pointwiseMult(d1, d2, 2 * n);
	p = recIDFT(d, 2 * n);
	return p;
}
/**
 * Wrapper de chamada da funcao FFT.
 */
double * evaluateDFT (double * p, int N){
	return recDFT(p, 2 * N);
}
/**
 * Funcao de multiplicacao ponto a ponto.
 * Dadas duas representacoes polinomiais p1 e p2 de N termos
 * cada uma, retorna um novo polinomio cujos coeficientes correspondem
 * ao produto escalar entre os vetores de coeficientes de p1 e p2.
 */
double * pointwiseMult (double * p1, double * p2, int N){
	double * p = calloc(N, sizeof(double));
	int i;
	for (i = 0; i < N; i++) p[i] = p1[i] * p2[i];
	return p;
}
/**
 * Funcao de operacao de FFT sobre uma representacao polinomial p
 * de N termos.
 */
double * recDFT (double * p, int N)
{
	double WN = cexp(I * 2 * M_PI);
	double W = 1;
	double *p1, *p2;
	double *d1, *d2, *d;
	int k;
	if (N == 1)	return copyVec(p, N);
	p1 = computeP1(p, N);
	p2 = computeP2(p, N);
\end{minted}
\end{listing}
\newpage
\begin{listing}[H]
\setcounter{listing}{2}
\caption{Método FFT: $O(n \lg n \lg \lg n)$}
\label{FFT}
\ContinuedFloat
\begin{minted}
[
frame=single,
framesep=2mm,
baselinestretch=1.2,
bgcolor=bg,
fontsize=\footnotesize,
linenos,
firstnumber=47,
]
{c}
	d1 = recDFT(p1, N / 2);
	d2 = recDFT(p2, N / 2);
	d = calloc(N, sizeof(double));
	for (k = 0; k < N / 2; k++){
		d[k] = d1[k] + W * d2[k];
		d[k + N / 2] = d1[k] - W * d2[k];
		W = W * WN;
	}
	return d;
}
/**
 * Dado um vetor v de tamanho N, retorna uma copia sua.
 */
double * copyVec (double * v, int N){
	double *newV = malloc(N * sizeof(double));
	int i;
	for (i = 0; i < N; i++) newV[i] = v[i];
	return newV;
}
/**
 * Dada uma representacao polinomial p de N termos, retorna a primeira
 * parcela da decomposicao de p (envolvendo somente os termos de ordem
 * par).
 */
double * computeP1 (double * p, int N){
	double * p1 = calloc(N / 2, sizeof(double));
	int i;
	for (i = 0; i < N / 2; i++)		p1[i] = p[2 * i];
	return p1;
}
/**
 * Dada uma representacao polinomial p de N termos, retorna a segunda
 * parcela da decomposicao de p (envolvendo somente os termos de ordem
 * impar).
 */
double * computeP2 (double * p, int N){
	double * p2 = calloc(N / 2, sizeof(double));
	int i;
	for (i = 0; i < N / 2; i++)		p2[i] = p[2 * i + 1];
	return p2;
}
\end{minted}
\end{listing}


\begin{listing}[H]
\ContinuedFloat
\setcounter{listing}{3}
\caption{Método FFT: $O(n \lg n \lg \lg n)$}
\label{FFT}
\begin{minted}
[
frame=single,
framesep=2mm,
baselinestretch=1.2,
bgcolor=bg,
fontsize=\footnotesize,
linenos,
firstnumber=88
]
{c}
/**
 * Funcao que divide todos os N elementos de um vetor v por scale.
 * Deve ser usada pela funcao de FFT inversa.
 */
void vecScale (double * v, int N, int scale){
	int i;
	for (i = 0; i < N; i++){
		v[i] = v[i] / N;
	}
}
/**
 * Funcao de operacao de FFT inversa sobre uma representacao polinomial
 * p de N termos. O resultado  eh reescalado corretamente.
 */
double * recIDFT (double * p, int N){
	double WN = cexp(- I * 2 * M_PI);
	double W = 1;
	double *p1, *p2;
	double *d1, *d2, *d;
	int k;
	if (N == 1)	return copyVec(p, N);
	p1 = computeP1(p, N);
	p2 = computeP2(p, N);
	d1 = recDFT(p1, N / 2);
	d2 = recDFT(p2, N / 2);
	d = calloc(N, sizeof(double));
	for (k = 0; k < N / 2; k++){
		d[k] = d1[k] + W * d2[k];
		d[k + N / 2] = d1[k] - W * d2[k];
		W = W * WN;
	}
	vecScale(d, N, N);
	return d;
}
\end{minted}
\end{listing}
\newpage
\section{Resultados}
%Uma seção descrevendo os resultados computacionais obtidos, incluindo tabelas, gráficos e outras ferramentas que você considere úteis para a clareza do texto. Não esqueça de detalhar em que plataforma (hardware e software) os experimentos foram executados (CPU, memória, versão de compilador, flags especiais usados na compilação, etc.).
\color{red}{\textbf{!FALTANDO!}}
\subsection{{\color{red}Execução com dados e observação dos resultados}}
\section{Conclusão}
%Uma seção de conclusão, descrevendo o que você aprendeu com os experimentos
\color{red}{\textbf{!FALTANDO!}}
\color{black}
\section{Referências}
%\section{OUTROS}
% Outras seções, a critério do grupo.
\bibliographystyle{apalike}
\bibliography{reference.bib}
\end{document}
